\documentclass[submission]{FPSAC2017}

\articlenumber{55}
\addbibresource{55_Nenashev_Kirillov.bib}

\newcommand{\Dim}{\textrm{dim}}
\newcommand{\Deg}{\textrm{deg}}
\newcommand{\Det}{\textrm{det}}
\newcommand{\Supp}{\textrm{supp}}
\newcommand{\Span}{\textrm{span}}

\newcommand {\bC} {\mathbb {C}}
\newcommand {\bR} {\mathbb {R}}
\newcommand {\bZ} {\mathbb {Z}}
\newcommand {\bQ} {\mathbb {Q}}
\newcommand {\bCP} {\mathbb {CP}} 
\newcommand {\bK} {\mathbb {K}} 
\newcommand {\bF} {\mathbb {F}}
\newcommand {\bN} {\mathbb {N}} 

\newcommand{\A} {\mathcal{A}} 
\newcommand{\B} {\mathcal{B}}
\newcommand{\C} {\mathcal{C}}
\newcommand{\D} {\mathcal{D}} 
\newcommand{\F} {{\mathcal{F}}}
\newcommand{\G} {{\mathcal{G}}}
\newcommand{\HH} {{\mathcal{H}}}
\newcommand{\I} {\mathcal{I}}
\newcommand{\J} {\mathcal{J}}
\renewcommand{\bK} {\mathcal{K}}

\newcommand{\tX}{\widetilde{X}}
\newcommand{\tY}{\widetilde{Y}}
\newcommand{\tZ}{\widetilde{Z}}

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma} \newtheorem{definition}{Definition}
\newtheorem{notation}[definition]{Notation}
\newtheorem{corollary}{Corollary} \newtheorem{example}{Example}

\newtheorem{remark}{Remark} \newtheorem{cor}{Corollary}

\newtheorem{question}{Question}
\newtheorem{conjecture}[question]{Conjecture} 
\newtheorem{claim}{Claim}
\newtheorem*{nota}{Notations}
\newtheorem{problem}[question]{Problem}

\usepackage{lipsum}
\makeatletter
\DeclareRobustCommand{\cev}[1]{%
  \mathpalette\do@cev{#1}%
}
\newcommand{\do@cev}[2]{%
  \fix@cev{#1}{+}%
  \reflectbox{$\m@th#1\vec{\reflectbox{$\fix@cev{#1}{-}\m@th#1#2\fix@cev{#1}{+}$}}$}%
  \fix@cev{#1}{-}%
}
\newcommand{\fix@cev}[2]{%
  \ifx#1\displaystyle
    \mkern#23mu
  \else
    \ifx#1\textstyle
      \mkern#23mu
    \else
      \ifx#1\scriptstyle
        \mkern#22mu
      \else
        \mkern#22mu
      \fi
    \fi
  \fi
}

\makeatother


\title[On $Q$-deformations of Postnikov-Shapiro algebras]{On $Q$-deformations of Postnikov-Shapiro algebras}

\author[A. N. Kirillov and G. Nenashev]{Anatol N. Kirillov\thanks{\href{mailto:kirillov@kurims.kyoto-u.ac.jp}{kirillov@kurims.kyoto-u.ac.jp}}\addressmark{1} \and Gleb Nenashev\thanks{\href{mailto:nenashev@math.su.se}{nenashev@math.su.se}}\addressmark{2}}

\address{\addressmark{1}Research Institute for Mathematical Sciences
Kyoto University,
Japan \\
  \addressmark{1}{The Kavli Institute for the Physics and Mathematics of 
the Universe, Kashiwa, Japan}\\
\addressmark{2}Department of Mathematics,
   Stockholm University,
    Sweden}

\received{\today}


\abstract{For any given loopless graph $G$,  we introduce $Q$ - deformations of its Postnikov-Shapiro algebras counting spanning trees and forests. We determine the total dimension of the algebras; our proof also gives a new proof of the formula for the total dimensions of the usual Postnikov-Shapiro algebras.}

\resume{Pour tout graphe sans boucles $G$, nous introduisons $Q$ - d{\'e}formations de ses alg{\`e}bres de Postnikov-Shapiro comptant les arbres et les for{\^e}ts. Nous d{\'e}terminons la dimension totale des alg{\`e}bres; notre preuve donne aussi une nouvelle preuve des dimensions des alg{\`e}bres usuelles de Postnikov-Shapiro.}

\keywords{Commutative algebra, Spanning trees and forests, Score vectors}


\begin{document}

\maketitle 

\section{Introduction and main results}

The Postnikov-Shapiro algebras (PS-algebras for short) have been introduced 
and studied in~\cite{PS}. There are a few generalizations of those algebras: in~\cite{AP} and~\cite{HR}, under the name {\it zonotopal algebras}, a generalization of PS-algebras  algebra was introduced for (real) arrangements.  In fact, 
this topic has its origin in earlier papers~\cite{SS} and~\cite{PSS}, which 
were motivated by the following problem  posed by V.\,Arnold in~\cite{Ar}:  

 Describe algebra $ {\mathcal{C}_n}$  generated by the curvature forms of tautological Hermitian linear bundles over the type $A$ complete flag variety ${\mathcal{F}}l_n$.

Surprisingly enough, it was observed and conjectured in \cite{SS}, that 
$\dim_{Q} {\mathcal{C}}_n= {\mathcal{F}}_n$, where ${\mathcal{F}}_n$ denotes 
the number of spanning forests of the complete graph $K_n$  on $n$ labeled vertices.   This conjecture has been proved in \cite{PSS}, and became a starting 
point for a wide variety of generalizations, including discovery of PS-algebras.      


The PS-algebras have a number of interesting properties, including an explicit formula for their Hilbert polynomials. Also these algebras are related to Orlik-Terao~algebras~\cite{OTe}, for more details, see for example~\cite{B}.
\newpage
 In our paper we will use the following basic notation:
\begin{notation}
{\rm We fix a field of zero characteristic $\bK$ (for example $\bC$ or~$\bR$).


We will work only with graphs without loops, but possibly with multiple edges.  We denote by 
$E(G)$ and $V(G)$ the set of edges and vertices of $G$ respectively. The  cardinalities of  $E(G)$ and $V(G)$ are denoted by $e(G)$ and $v(G)$ respectively. The number of connected components of $G$ is denoted by $c(G)$. 

 We denote the set $\{1,2,\ldots,(a-1),a\}$ by $[a]$.
}
\end{notation}

The following  algebra $\C_G$  (counting spanning forests)  associated to an arbitrary vertex-labeled graph $G$ was introduced in  \cite {PS}.
 Let $G$ be a graph without loops on the vertex set $[n].$ 
Let  $\Phi_G$ be the graded commutative algebra over $\bK$ 
generated by the variables $\phi_e, e \in G$, with the defining relations:
$$(\phi_e)^2 = 0, \quad \text {for every edge}\; e\in G.$$
Let $\C_G$ be the subalgebra of  $\Phi_G$ generated by the elements
$$X_i =\sum_{e\in G} c_{i,e} \phi_e,$$
for  $i \in  [n], $ where 
\begin{equation}\label{eq:def_cie}
c_{i,e}=\begin{cases} \;\;\;1\quad \text{if}\; e=(i,j),\ i<j;\\
                                            -1\quad\text{if}\; e=(i,j),\ i>j;\\
                                             \;\;\;0\quad \text{otherwise}.
\end{cases}
\end{equation}
Observe that we
 assume that $\C_G$ contains $1$.

\medskip

Let us describe all relations between $X_i$.
{\rm Namely given a graph $G$,
consider the ideal $J_{G}$ in the ring $\bK[x_1,\cdots,x_n]$ generated by
$$p_I=\left(\sum_{i\in I} x_i\right)^{ d_I+1},$$
where $I$ ranges over all nonempty subsets of vertices, and $d_I$ is the total number of edges between vertices in $I$ and vertices outside~$I$, i.e., belonging to $V(G)\setminus I$.  Define the algebra   ${\B}_G$ as the quotient $\bK[x_1,\dots,x_n]/ J_{G}.$}


\begin{theorem}[cf.~\cite{PS}]
\label{thm:PS}

 For any graph $G$, the algebras  ${\B}_{G}$ and ${\C}_{G}$ are isomorphic,
 their total dimension over $\bK$ is equal to the number of spanning forests in $G$.


Moreover, the dimension of the $k$-th graded component of these algebras  equals
the number of spanning forests $F$ of $G$ with external activity $e(G)-e(F)-k$.
\end{theorem}

In particular, the second part of \cref{thm:PS} implies that the Hilbert polynomial of ${\C}_{G}$ is a specialization of the Tutte polynomial 
of~$G$.   
\begin{corollary}
Given a graph $G$, the Hilbert polynomial $\HH_{C_G}(t)$ of the algebra $\C_G$ is given by
$$\HH  _{\C_G}(t)=T_G\left(1+t,\frac{1}{t}\right)\cdot t^{e(G)-v(G)+c(G)}.$$ 
\end{corollary}
In the recent paper~\cite{Ne} the second author found the following important property of these algebras.
\begin{theorem}[cf.~\cite{Ne}] Given two graphs $G_1$ and $G_2,$ the algebras $\C_{G_1}$ and $\C_{G_2}$ are isomorphic  if and only if the graphical matroids of $G_1$ and $G_2$ coincide. (The  isomorphism can be thought of as either graded or non-graded, the statement holds in both cases.) 
\end{theorem}


Furthermore, the paper~\cite{NS} contains a "K-theoretic" filtered structure of these algebras, which  distinguishes graphs (see definition inside there).

\bigskip

The main object of study of the present paper  is a family of $Q$-deformations of  $\C(G)$ which we define as follows. For a graph $G$  and a set  of parameters $Q=\{q_e\in \bK: \ e\in E(G)\}$, define 
 $\Phi_{G,Q}$ as the commutative algebra generated by the variables $\{u_e : \ e\in E(G)\}$ satisfying 
 $$u_e^2=q_eu_e,\; \text{for every edge\; } e\in G.$$

Let $V(G)=[n]$ be the vertex set  of a graph $G.$ Define the \emph{$Q$-deformation} $\Psi_{G,Q}$ of $\C_G$ as the filtered subalgebra of $\Phi_{G,Q}$ generated by the elements:
$$X_i=\sum_{e: \ i\in e} c_{i,e}  u_e, \ i\in[n],$$
where $c_{i,e}$ are the same as in~\eqref{eq:def_cie}. The filtered structure on $\Psi_{G,Q}$ is induced by the elements $X_i,\; i\in[n]$. More concretely, the filtered structure is an increasing sequence   $$\bK= F_0\subset F_1\subset F_2\ldots \subset F_m=\Psi_{G,Q}$$ of subspaces of $\Psi_{G,Q}$, where $F_{k}$ is the linear span of all monomials $X_1^{\alpha_1}X_2^{\alpha_2}\cdots X_n^{\alpha_n}$ such that $\alpha_1+\ldots+\alpha_n\leq k$. Note that algebra $\Phi_{G,Q}$ has a finite dimension, then $\Psi_{G,Q}$ has a finite dimension, which gives that the increasing sequence of subspaces is finite.  
The Hilbert polynomial of a filtered algebra is the Hilbert polynomial of the associated graded algebra, it has the following formula
 $$\HH(t)=1+\sum_{i=1} (dim(F_i)-dim(F_{i-1}))t^i.$$
 
\smallskip
 In the case when all parameters coincide, i.e., $q_e=q$, $\forall e\in G,$  we denote the corresponding algebras by  $\Psi_{G,q}$ and $\Phi_{G,q}$ respectively We refer to $\Psi_{G,q}$ as the {\it Hecke deformation} of $\C_G$.

 \begin{remark}{\rm (i)}
By definition, the algebra $\Psi_{G,0}$ coincides with  $\C_G$. 

{\rm (ii)}
If we change the signs of $q_e,\ e\in E'$ for some subset $E'\subseteq E$ of edges, we obtain an isomorphic algebra. 

{\rm(iii)} It is possible to write relations such as $u_e^2=\beta_e$ or $u_e^2=q_e u_e+\beta_e$  where ${\beta_e\in \bK}$. 
But in the case of algebras counting spanning trees we need relations without constant terms, see \cref{final}.
\end{remark}


 



\begin{example}
\emph{(i)} Let $G$ be a graph with two vertices, a pair of (multiple) edges $a$, $b$. Consider the Hecke deformation of its $\C_G$, i.e., satisfying $q_{a}=q_{b}=q$.

\smallskip 
The generators are $X_1=a+b,\; X_2=-(a+b)=-X_1.$ One can easily check that the filtered structure is given by
$$F_0={<}1{>};\ \ F_1={<}1,\ a+b{>};\ \ F_2={<}1,\ a+b,\ ab{>}.$$
The Hilbert polynomial $\HH  (t)$ of $\Psi_{G,q}$ is given by 
$$\HH  (t)=1+t+t^2.$$
 The defining relation for $X_1$  is given by
 $$X_1(X_1-q)(X_1-2q)=0.$$


\noindent
\emph{(ii)} For the same graph as before, consider the case when $Q=\{q_a,q_b\},\;q_{a}^2\neq q_{b}^2$.

The generators are the same: $X_1=a+b$, $X_2=-(a+b)=-X_1$. 
Since 
\begin{multline*}X_1^3=q_a^2a+q_b^2b+3(q_a+q_b)ab=\frac{3(q_a+q_b)}{2}X_1^2-\frac{q_a^2+3q_b^2}{2}a-\frac{3q_a^2+q_b^2}{2}b\\
=\frac{3(q_a+q_b)}{2}X_1^2-\frac{3q_a^2+q_b^2}{2}X_1+(q_a^2-q_b^2)a,
\end{multline*}
we have $$ F_0={<}1{>};\ \ F_1={<}1,\ a+b{>};\ \ F_2={<}1,\ a+b,\ q_aa+q_bb+2ab{>};\ \ F_3={<}1,\ a,\ b,\ ab{>}.$$
The Hilbert polynomial $\HH  (t)$ of $\Psi_{G,Q}$ is given by 
$$\HH  (t)=1+t+t^2+t^3.$$ 
Observe that in this case the algebra $\Psi_{G,Q}$ coincides with  the whole $\Phi_{G,Q}$ as a linear space, but has a different filtration.
 The defining relation for $X_1$  is given by
 $$X_1(X_1-q_a)(X_1-q_b)(X_1-q_a-q_b)=0.$$
\end{example}


\medskip


The first result of the present paper is about Hecke deformations. 
\begin{theorem}
\label{thm:same}
For any loopless graph $G$, filtrations of  its Hecke deformation $\Psi_{G,q}$  induced by $X_i$ and induced by the algebra $\Phi_{G,q}$  coincide. Furthermore, the Hilbert polynomial $\HH  _{\Psi_{G,q}}(t)$ of this filtration is given by 
$$\HH  _{\Psi_{G,q}}(t)=T_G\left(1+t,\frac{1}{t}\right)\cdot t^{e(G)-v(G)+c(G)},$$
i.e., it coincides with that of $\C_G$.
\end{theorem} 




\medskip
The latter result implies that cases when not all   $q_e$ are equal are  more interesting than the case of the Hecke deformation. 
We will work with weighted graphs, i.e. when each edge $e$ has non-zero $q_e\in \bK$, and will simply denote the algebra  for a weighted graph $G$ by $\Psi_G$.

\begin{definition}For a loopless weighted graph $G$ on $n$ vertices and an orientation $\vec{G},$ define the score vector $D_{\vec{G}}^+\in\bK^n$ as follows
$$\Bigg(\sum_{\substack{e\in E:\\ end(\vec{e})=1}}q_e, \sum_{\substack{e\in E:\\ end(\vec{e})=2}}q_e,\ldots, \sum_{\substack{e\in E:\\ end(\vec{e})=n}}q_e \Bigg),$$
where $end(\vec{e})$ is the final vertex of oriented edge $\vec{e}$.
\end{definition}
\begin{theorem}
\label{thm:different}
 For any loopless weighted graph $G$, the dimension of the algebra $\Psi_G$ is equal to the number of distinct score vectors, i.e.
$$dim(\Psi_G)=\#\{D\in\bK^n:\ \exists \vec{G} \text{\ such that }D=D_{\vec{G}}^+ \}.$$
\end{theorem}

\smallskip

As a consequence of \cref{thm:same,thm:different}, we obtain the following known property.  (See bijective proofs in~\cite{KW} and~\cite{Be}.)
\begin{corollary}\label{cor:forests=orient}
For any graph $G$, the number of its spanning forests is equal to the number of distinct vectors of incoming degrees corresponding to its orientations.
\end{corollary}
Our proof of \cref{thm:different} is very simple and it gives a new proof about total dimension of an original algebra.
Unfortunately, our proof works only for weighted graphs (nonzero parameters). A zero parameter does not play role in score vectors, so we do not even have a conjecture.
\begin{problem}
What is the dimension of $\Psi_{G,Q}$ in the case when some of $q_e$ are non-zero and few  are zero?
\end{problem}










\bigskip 

The structure of the paper is as follows. 
 In \cref{sec:hecke} we prove \cref{thm:same} and discuss Hecke deformations. In \cref{basis} we describe the basis  of $Q$-deformations and  present a  proof of \cref{thm:different}. In \cref{experiments} we consider "generic" cases and provide  examples of Hilbert polynomials. In \cref{final} we present 
 $Q$-deformations of the Postnikov-Shapiro algebra which counts spanning trees instead of spanning forests.

       



\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Hecke deformations}\label{sec:hecke}
\begin{proof}[Sketch of proof of \cref{thm:same}]
To settle  this theorem, we need to show that if an element $y\in\Psi_{G,Q}$ has degree $d,$ then it has the same degree in $\Phi_{G,Q}$.

Assume the opposite; then there exists an element $y=f(X_1,\ldots,X_n)$, where $f$  is a polynomial of degree $d$, but $y$ has degree less than $d$  in its representation in terms of the edges $u_e,$ $e\in G$.

Rewrite $f$ as $f=f_d+f_{<d}$, where $f_d$ is a homogeneous polynomial of degree $d$ and  $\deg f_{<d} <d$.

Let $\widehat{X}_1,\ldots,\widehat{X}_n$ be the elements in the algebra ${\mathcal{C}}_G=\Psi_{G,0}$ corresponding to the vertices. 
 We conclude that $f_d(\widehat{X}_1,\ldots,\widehat{X}_n)$ should vanish. Indeed, otherwise  $\deg f_d({X}_1,\ldots,X_n)=d$  in $\Phi_{G,Q}$ and $\deg f_{<d}({X}_1,\ldots,X_n)<d$ which implies that  $\deg f({X}_1,\ldots,X_n)=d$  in $\Phi_{G,Q}$.
 
By \cref{thm:PS}, we know all  the relations between $\{\widehat{X}_1,\ldots,\widehat{X}_n\}.$ Namely, they are of the  form $(\sum_{i\in I}\widehat{X}_i)^{d_I+1}$, where $I$ is an arbitrary subset of vertices and $d_I$ is the number of edges between $I$ and its complement $V(G)\setminus I$.


Using this, we obtain
$$f_d(x_1,\ldots,x_n)=\sum_{\substack{I\subseteq V(G):\\ d_I\leq d-1}} r_{I}(x_1,\ldots,x_n)\cdot \left(\sum_{i\in I}x_i\right)^{d_I+1},$$
where $r_I$ is a homogeneous polynomial of degree $d-d_I-1$.
However, it is possible to rewrite   $\left(\sum_{i\in I}X_i\right)^{d_I+1}$ as an element of a smaller degree in terms of $\{X_i,\ i\in I\}$. Hence, there is polynomial $g$ of degree less than $d$ such that $y=g(X_1,\ldots,X_n)$.


\smallskip



The second part follows from the first one. It is enough to consider graded lexicographic orders of monomials in $\{u_e,\ e\in G\}$ and $\{\phi_e,\ e\in G\}$. For these orders, we have a natural bijection between the Gr{\"o}bner bases of $\Psi_{G,q}$  and of ${\mathcal{C}}_G$. Hence, their Hilbert polynomials coincide.
\end{proof}

\medskip


\cref{cor:forests=orient} shows that the dimension of a Hecke deformation is equal to the number of lattice points of the zonotope $Z\in \bR^n$, which is the Minkowski sum of edges, i.e,
$$Z_G:=\bigoplus_{e\in G}I_e,$$
where, for edge $e=(i,j)$, $I_e$ is the segment between points $(\underbrace{0,\dots, 0}_{i-1},1,0,\ldots,0)$  and $(\underbrace{0,\dots, 0}_{j-1},1,0,\ldots,0)$. In~\cite{HR} Holtz and Ron defined the zonotopal algebra for any lattice zonotope, whose dimension is equal to the number of lattice points. 
By their definition PS-algebra ${\B}_{G}$ is the zonotopal algebra corresponding to $Z_G$. We think that Hecke deformations should be extended on a case of zonotopal algebras.
\begin{problem}
Define Hecke deformations of zonotopal algebras.
\end{problem}

Since there is no definition of zonotopal algebras in terms of square-free algebras, we should work with quotient algebras. 
In the case of Hecke deformations of PS-algebras \cref{prop:ann} from  \cref{basis} gives all defining relations between elements $X_i,\ i\in[n].$ 
\begin{theorem}
\label{thm:quo-Hecke}
Let $G$ be a graph and $q\in \bK$ ($q_e=q,\ \forall e\in G$). Then all defining relations between $X_i,\ i\in [n]$ are given by
$$\prod_{k=-\vec{d}_I}^{\cev{d}_I}\left(\sum_{i\in I} X_i -qk\right)=0,$$
where $I$ is any subset of vertices and $\vec{d}_I$ (respectively $\cev{d}_I$) is the number of edges $e=(i,j)\in G:\ i\in I,\ j\notin I$ and $i>j$ (respectively $i<j$).  
\end{theorem}



\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Basis of  $Q$-deformations}\label{basis} For the next proofs, we need to describe a basis of the algebra $\Phi_G$. For a subset $E'$ of the edges, we define $$\alpha_{E'}=\prod_{e\in E'}\frac{u_e}{q_e}.$$
Since $q_e\neq 0$ this basis is well defined. For an element $z=\sum_{E'} z_{E'}\alpha_{E'}\in \Phi_G$, we define the vector $\widetilde{z}=[\widetilde{z}_{E'}]_{E'\subseteq E}\in \bK^{2^{e(G)}},$ where
$$\widetilde{z}_{E'}=\sum_{E''\subseteq E'}z_{E''}.$$
It is clear that from this vector we can reconstruct $z$, also it is easy to describe the product on these coordinates. Furthermore the unit element $I$ is given by $I:=\widetilde{1}=[1]_{E'\subseteq E}.$
\begin{lemma}\label{lem:basis} Elements corresponding to $[0,\ldots,0,1,0,\ldots,0]$ form a linear basis of~$\Phi_G$. This basis has the following property: let $y,z\in \Phi_G,$ be elements of the algebra, then the sum of elements is the sum by coordinates
$$\widetilde{(y+z)}=\widetilde{y}+\widetilde{z},$$
and the product is the Hadamard product of coordinates
$$\widetilde{(yz)}=\widetilde{y}\circ \widetilde{z}.$$
\end{lemma}


Consider the following bijection between subsets of $E(G)$ and orientations of $G$.
For the subset $E'\subseteq E$ we define the following orientation: if $e\in E'$, then the orientation is from the biggest end to the smallest, otherwise the orientation is the opposite.


\begin{lemma}
\label{lem:Xi}
The element $X_i$ in coordinates is given by
$$\widetilde{X}_i
=\begin{bmatrix}\makebox[4em]{}\\
\begin{aligned}
 D_{\vec{G}}^+(i)
\end{aligned}
\\
\makebox[4em]{} \end{bmatrix}_{\vec{G}} - \left(\sum_{\substack{e\in E:\\
c_{i,e}=-1}} q_e\right) \cdot I,$$
where $D_{\vec{G}}^+(i)$ is $i$-th coordinate of a score vector $D_{\vec{G}}^+$.
\end{lemma}
 



We use in the proof of \cref{thm:different} the following elements $$\widetilde{A}_i:
=\begin{bmatrix}\makebox[4em]{}\\
\begin{aligned}
 D_{\vec{G}}^+(i)
\end{aligned}
\\
\makebox[4em]{} \end{bmatrix}_{\vec{G}}.$$
We need another technical lemma.
\begingroup\emergencystretch=10em
\begin{lemma}
\label{lem:dim}
For an element $R\in \Phi_G$, the dimension of the space generated by $R$ (i.e, 
$\Span{{<}1,R,R^2,\ldots{>}}$) is equal to the number of different coordinates of the vector $\widetilde{R}$.
\end{lemma}
\endgroup
 

Now we can prove \cref{thm:different}.
\begin{proof}[Proof of \cref{thm:different}]
By \cref{lem:Xi} we can change the set of generators $X_i,\ i\in V(G)$ to the set $A_i,\ i\in V(G)$.
If two orientations have the same score vector, then the corresponding coordinates in $\I$ and in $\widetilde{A}_i,\ i\in V(G)$ coincide. Using \cref{lem:basis}, we get that they coincide for any element from algebra $\Psi_G$, hence,  $$dim(\Psi_G)\leq \#\{D\in\bK^n:\ \exists \vec{G} \text{\ such that }D=D_{\vec{G}}^+ \}.$$
For the converse, we consider an element $$R=r_0 + r_1 A_1+\ldots +r_nA_n, $$
where $r_i\in \bQ$ and are generic. 

The coordinates $\widetilde{R}$ are non-zero and, for two orientations, they coincide if and only if their score vectors coincide. Then, by \cref{lem:dim} the dimension of the subalgebra generated by $R$ is equal to number of different score vectors. Since $R$ belongs to $\Psi_G$, we obtain 
$$dim(\Psi_G)\geq \#\{D\in\bK^n:\ \exists \vec{G} \text{\ such that }D=D_{\vec{G}}^+ \},$$
which with the upper bound gives equality.
\end{proof}



\bigskip

Using \cref{lem:dim}
 we can calculate the minimal annihilating polynomial for any linear combination of vertices.
\begin{proposition}
\label{prop:ann}
Given a weighted graph $G$, for an element $X\cdot t=X_1t_1+\ldots+X_nt_n,\ t\in \bK^n$  the minimal annihilating polynomial of it is given by
$$\prod_{s\in \D_I}\left(X\cdot t-s+z\right)=0,$$
where $${\D}_I=\{D_{\vec{G}}^+\cdot t:\  \ \vec{G}\}\ \ \ {\textrm and} \ \ \ z=\sum_{\substack{i,\ e:\\
c_{i,e}=-1}} q_e t_i.$$
\end{proposition}
In the case of Hecke deformations it gives all defining relations between $X_i,\ i\in V(G)$, see \cref{thm:quo-Hecke}.
\begin{problem}
Find all relations between $X_i,\ i\in V(G)$. In other words, define  $\Psi_{G,Q}$ 
as a quotient algebra of the polynomial ring.
\end{problem}

\bigskip

\section{Case $E=E_1\sqcup\ldots\sqcup E_k$ and generic $q_1,\ldots,q_k\in \bK$}
\label{experiments}

We cannot describe the Hilbert polynomial of $\Psi_{G,Q}$.  We suggest to start from the following type of algebras: when different parameters are in a generic position. In this case we know the total dimension in terms of forests.
\begin{theorem}
\label{thm:split}
Let $G$ be a graph,  given a partition $E=E_1\sqcup\ldots\sqcup E_k$ of edges and generic $q_1,\ldots,q_k\in \bK$ ($q_e=q_i$, for $e\in E_i$). Then the dimension of the algebra $\Psi_{G,Q}$ equals the number $k$-tuples of spanning forests such that $F_i\subseteq E_i$. In other words, 
$$\dim (\Psi_{G,Q})=\prod_{i=1}^k\#\{F\subseteq E_i\;\vert\quad  F\;\text{ is a forest}\}.$$
\end{theorem}

\begin{problem}
\label{ques:split}
What is the Hilbert polynomial $HS_{\Psi_{G,Q}}$ in the case $E=E_1\sqcup\ldots\sqcup E_k$ and generic $q_1,\ldots,q_k\in \bK$?

It seems that it is impossible to reconstruct the Hilbert polynomial  from the Tutte polynomial.
For example, let $G$ be the graph on two vertices with $k$ multiple edges, then its Tutte polynomial is given by $$T_G(x,y)=x+y+\ldots+y^{k-1},$$
and the Hilbert polynomial, when each edge has a self generic parameter is
$$HS_{\Psi_{G,Q}}=1+t+\ldots+t^{2^k-1}.$$
In each case it is not a specialization of the Tutte polynomial. 
\end{problem}

Here we present the Hilbert polynomial of algebras for complete graphs. Our tables correspond to algebras (1) with the same parameter; (2) with the same parameters except for one edge and (3) where all parameters are generic. By \cref{thm:split} we know their total dimensions, in the first case we also know the Hilbert polynomial.


\subsection{Hilbert polynomials of $\C_{K_n}$ and $\Psi_{K_n,q}$}

\begin{center}
    \begin{tabular}{ | l | l | l | l | l | l | l |  l | l | l | l | l|p{5cm} |}
    \hline
    Graph $\backslash \HH  (t)$  & $0$ & $1$  & $2$ & $3$  & $4$ & $5$ & $6$& $7$& $8$ & $9$& $10$ \\ \hline
    
    $K_2$& $1$ & $1$ & &&&&&&&& \\ \hline
    
   $K_3$& $1$ & $2$ & $3$ & $1$ & &&&&&& \\ \hline
   
   $K_4$& $1$ & $3$ & $6$ & $10$ & $11$ & $6$ & $1$ &&&&\\ \hline 
     
     $K_5$& $1$ & $4$ & $10$ & $20$ & $35$ & $51$ & $64$ & $60$ & $35$ & $10$ & $1$\\ \hline 
    \end{tabular}
\end{center}


\subsection{Hilbert polynomials of $\Psi_{K_n,Q}$, when $E_1=E(K_n)\backslash \{e\}$ and $E_2=\{e\}$}

\begin{center}
    \begin{tabular}{ | l | l | l | l | l | l | l |  l | l | l | l | l|  l|p{5cm} |}
    \hline
    Graph $\backslash  \HH  (t)$  & $0$ & $1$  & $2$ & $3$  & $4$ & $5$ & $6$& $7$& $8$ & $9$& $10$\\ \hline
    
    $K_2$& $1$ & $1$ & &&&&&&&&\\ \hline 
    
   $K_3$& $1$ & $2$ & $3$ & $2$ & &&&&&& \\ \hline 
   
   $K_4$& $1$ & $3$ & $6$ & $10$ & $13$ & $11$ & $4$&&&& \\ \hline 
    $K_5$& $1$ & $4$ & $10$ & $20$ & $35$ & $53$ & $72$ & $83$ & $72$ & $38$ & $8$\\ \hline 
     
    \end{tabular}
\end{center}



\subsection{Hilbert polynomials of $\Psi_{K_n,Q}$, when $Q$ is generic}
\label{table:generic}

\begin{center}
    \begin{tabular}{ | l | l | l | l | l | l | l |  l | l | l | l | l|  l|p{5cm} |}
    \hline
    Graph $\backslash \HH  (t)$  & $0$ & $1$  & $2$ & $3$  & $4$ & $5$ & $6$& $7$& $8$ & $9$ & $10$ & $11$\\ \hline
    
    $K_2$& $1$ & $1$ & &&&&&&&&&\\ \hline 
    
   $K_3$& $1$ & $2$ & $3$ & $2$ &&&&&&&& \\ \hline 
   
   $K_4$& $1$ & $3$ & $6$ & $10$ & $15$ & $19$ & $10$ &&&&&\\ \hline 
    $K_5$& $1$ & $4$ & $10$ & $20$ & $35$ & $56$ & $84$ & $120$ & $165$ & $220$ & $217$ & $92$ \\ \hline  
    \end{tabular}
\end{center}
Note that in the last case for $K_5$, the $11^\text{th}$ graded component is not empty, because otherwise the total dimension would be at most $1+4+10+..+220+286=1001$, but by \cref{thm:different} the total dimension is $2^{\binom{5}{2}}=1024$. 


\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Deformations of Postnikov-Shapiro algebras counting spanning trees}
\label{final}
To construct algebras counting spanning trees of $G$ we need to add to the algebra $\Phi_{G,Q}$ several relations  corresponding to cuts of $G$.
 
For a connected graph $G$ with fixed vertex $g\in V(G)$ and a set  of parameters $Q=\{q_e\in \bK: \ e\in E(G)\}$,  define 
 $\Phi_{G,Q}^T$ as the commutative algebra generated by the variables $\{u_e : \ e\in E(G)\}$ satisfying 
 $$u_e^2=q_eu_e,\; \text{for every edge\; } e\in G;$$
  $$\prod_{\substack{e=(i,j)\ i\in I, j\notin I:\\ c_{i,e}=1}} u_e\prod_{\substack{e=(i,j)\ i\in I, j\notin I:\\ c_{i,e}=-1}} (u_e-q_e)=0,\; \text{for every subset $ I\subseteq V(G)\setminus \{g\}$}.$$

Let $V(G)=[n]$ be the vertex set  of a graph $G.$ Define the algebra  $\Psi_{G,Q}^T$ as a filtered subalgebra of $\Phi_{G,Q}^T$ generated by the elements:
$$X_i=\sum_{e: \ i\in e} c_{i,e}  u_e, \ i\in[n],$$
where $c_{i,e}$ are the same as in~\eqref{eq:def_cie}.


\medskip
 In the case when  all parameters coincide, i.e., $q_e=q$, $\forall e\in G,$  we denote the corresponding algebras by  $\Psi_{G,q}^T$ and $\Phi_{G,q}^T$ respectively. The algebra $\Psi_{G,0}^T$ coincides with  $\C_G^T$, the dimension of $\C_G^T$ is equal to the number of spanning trees (see~\cite{PS}). We refer to $\Psi_{G,q}^T$ as the {\it Hecke deformation} of $\C_G^T$.
 


For these algebras, we have two similar theorems. The proof of \cref{thm:same-tree} is similar to \cref{thm:same}.
\begin{theorem}
\label{thm:same-tree}
For any loopless connected graph $G$, the filtrations of  its Hecke deformation $\Psi_{G,q}^T$  induced by $X_i$ and induced from the algebra $\Phi_{G,q}^T$  coincide. Furthermore the Hilbert polynomial $\HH  _{\Psi_{G,q}^T}(t)$ of this filtration is given by 
$$\HH  _{\Psi_{G,q}^T}(t)=\HH_{\C_G^T}(t)=T_G\left(1,\frac{1}{t}\right)\cdot t^{e(G)-v(G)+c(G)}.$$
\end{theorem}




\begin{definition}
Orientation $\vec{G}$ is  called a $g$-connected orientation if for  any vertex there is a path to $g$. The corresponding score vector $D_{\vec{G}}^+$ is called a $g$-connected score vector. \end{definition}
\begin{theorem}
\label{thm:different-tree}
 For any loopless weighted connected graph $G$ with a root $g$, the dimension of the algebra $\Psi_G^T$ is equal to the number of distinct $g$-connected score vectors.
\end{theorem}
The proof of \cref{thm:different-tree} is more complicated than \cref{thm:different}, the key idea is that $\Psi_{G}^T$ is a quotient algebra of $\Psi_{G}$.

Note that in \cref{thm:different-tree} (unlike \cref{thm:different}) it is not true that if we change signs of some $q_e$, the dimension remains the same. Also we do not have combinatorial analogue of \cref{thm:split}.



\begin{problem}
Let $G$ be a connected graph with a root $g$,  given a partition $E=E_1\sqcup\ldots\sqcup E_k$ of edges and generic $q_1,\ldots,q_k\in \bK$ ($q_e=q_i$, for $e\in E_i$).
Describe the dimension of the algebra $\Psi_{G,Q}^T$ in terms of trees and forests.
\end{problem}

\begin{remark}
We can construct $Q$-deformations of internal algebras (see definitions in~\cite{AP} and~\cite{HR}), although there is no definition of internal algebra in terms of edges. For this we should add relations also for subsets $I\ni g$. These algebras count strong-connected score vectors, see more details inside full version. 
\end{remark}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\acknowledgements{The authors want to thank Boris Shapiro for  useful discussions. The first author is grateful to the department of mathematics at Stockholm University for the hospitality in October 2016 when this project was carried out. }


\printbibliography




\end{document}
